package algorithm.leetcode.medium;

/*
 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
 */

import java.util.Stack;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/22
 */
public class Question402 {

    public static void main(String[] args) {

    }

    /**
     * 思路：贪心算法
     * 删除的数字应该尽量在高位，则当前位小于前一位时，对前一位出栈，当前位入栈。
     */
    public String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        }
        char[] chars = num.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char ch : chars) {
            while (!stack.isEmpty() && ch < stack.peek() && k > 0) {
                // 后一位小于前一位
                stack.pop();
                k--;
            }
            // 防止出现0开头
            if (stack.isEmpty() && ch == '0') {
                continue;
            }
            stack.push(ch);
        }

        // 继续移除
        while (k > 0) {
            stack.pop();
            k--;
        }

        if (stack.isEmpty()) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        // 因为是stack需要反转下
        return sb.reverse().toString();
    }
}
